package com.company.algo.niuke;

/**【会做一半】
 给定两个字符串str1和str2，输出两个字符串的【最长公共子序列】。如果最长公共子序列为空，则返回"-1"。
 题目要求输出子序列而非长度，所以需要在求最长公共子序列长度的基础上进行字符串拼接，拼接依据为dp[i][j]
 定义：dp[i][j]: 以下标i-1为结尾的s1和以下标j-1为结尾的s2，最长公共子序列的长度
 转移：dp[i][j] =
        1. s1[i]==s2[j],则dp[i][j] = dp[i-1][j-1] + 1;
        2. s1[i]!=s2[j],则需要判断s1[i-1]/s1[i]和s2[j]/s2[j-1]是否相同，即dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
 初始化,dp[i][0] = 0, dp[0][j] = 0
 基于dp结果数组，拼接字符串
 i=len1,j=len2;
 if(s1[i]==s2[j])->res.append(s1[i]),i--,j--
 if(dp[i-1][j]>dp[i][j-1]): 说明s1[i-1]可缺省,不是最长公共子序列中的元素，i--（跳过）
 else                     : 说明s2[j-1]可缺省，j--（跳过）
 */
public class LongestCommonSubseq2 {
    public String LCS(String s1, String s2){
        /*step one: get LCS length*/
        int len1 = s1.length();
        int len2 = s2.length();
        int[][] dp = new int[len1+1][len2+1];
        for (int i = 1; i <= len1; i++) {
            for (int j = 1; j <= len2; j++) {
                if (s1.charAt(i-1)==s2.charAt(j-1)) dp[i][j] = dp[i-1][j-1] + 1;
                else dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
            }
        }
        /*step two: append str by dp[][]*/
        int i = len1, j=len2;
        StringBuilder res = new StringBuilder();
        while (i>0 && j>0){
            if (s1.charAt(i-1)==s2.charAt(j-1)) {
                res.append(s1.charAt(i-1));
                i--;
                j--;
            }
            else if (dp[i-1][j]>dp[i][j-1]) i--;
            else j--;
        }
        if (res.length()==0) return "-1";
        return res.reverse().toString();
    }

}
